package com.fmm.hard;

public class RegularExpression {

    /**
     * @param s 待匹配的字符串
     * @param p 正则表达式，只允许 "*"、"?"、"a-z"
     * @return 是否匹配
     * */
    public static boolean isMatch(String s, String p) {
        // 初始化动态规划矩阵，dp[i][j] 表示 p 的前 i 个字符和 s 的前 j 个字符是否匹配
        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
        for (int i = 0; i < p.length() + 1; i++) {
            for (int j = 0; j < s.length() + 1; j++) {
                if (i == 0 && j == 0) {
                    // p 和 s 都为空时，匹配成功。
                    // 为什么初始化成 true? 因为这个值影响到 p[1] 和 s[1]相等时，使用的是这个值！
                    dp[i][j] = true;
                } else if (i == 0) {
                    // i = 0 的时候，表示任意字符串是否匹配 “空” 表达式，所以初始化为 false！
                    dp[i][j] = false;
                } else if (j == 0) {
                    // j = 0 的时候，表示空字符串是否匹配表达式，只有当表达式的字符为 * 时 同时 去掉当前这个 * 也为 ture 时才是true！
                    dp[i][j] = p.charAt(i - 1) == '*' && dp[i - 1][j];
                } else {
                    // 状态转移方程
                    if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (p.charAt(i - 1) == '*') {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[p.length()][s.length()];
    }

    public static void main(String[] args) {
        String s = "aa";
        String p = "a";
        System.out.println(isMatch(s, p));

        s = "aa";
        p = "*";
        System.out.println(isMatch(s, p));

    }
}
